home *** CD-ROM | disk | FTP | other *** search
Text File | 1995-07-29 | 17.0 KB | 592 lines | [TEXT/KAHL] |
- /*======================================================
- PackPresents()
-
- Clement James Goebel III.
- Programmers Challenge Dec 93 issue
-
- ------------------------------------------------------
- This code accepts a number of presents one after
- another and attempts to store as MANY as possible
- in its storage area. This routine starts with an
- array describing the expected distribution of data
- and then slowly changes to use an array that
- describes the sizes of observed presents as the
- process continues. These arrays are used to decide
- which presents are too big and should not be
- stored as they will cause us to throw away smaller
- presents latter. The routine is slow and methodical
- as it trys to pack presents into the smallest
- spaces it can find. It also does an ok job of
- guessing which packages to discard, a function
- that might not really be needed with evenly
- distributed data sets. But the goal was to pack the
- most, so you can't be too careful.
-
- The matrix that keeps track of stored presents
- contains zeros where presents are stored, and all
- other locations contain a value that represents the
- amount of free space that is contiguous to that
- location. We will always try to fill small holes
- first, a better way might be to look for presents
- that are half the size of the hole, but that would
- require many more special cases. And when placing
- presents we will always try to get as many surfaces
- to touch as possible.
- ------------------------------------------------------*/
-
- #include "stdio.h"
-
- #define PRINTF 0 /* display debug info */
-
- #define WID_DIM 100
- #define LEN_DIM 100
-
- #define MIN_GIFT_DIM 5
- #define MAX_GIFT_DIM 15
-
- #define LIKES_OTHERS 3
- #define LIKES_WALLS 2
-
- #define SPACE_USED 0
- #define MEASURING -1
-
- static short sgsGiftsSeen;
- static short sgsGiftsStored;
- static long sglExpectedCount;
- static short sgsLeftmostPresent;
- static short sgsTopmostPresent;
- static long sglItemsOnStack;
- static long sglTotalAreaExpected;
- static short *sgasStack;
- static short *sgasAreasSeen;
- static short *sgasAreasExpected;
- static long *sgalSpace;
-
- /*------------------------------------------------------
- Function defs. User calls PackPresents
- ------------------------------------------------------*/
- typedef void (*NextPresProc)
- (unsigned short *pWidth, unsigned short *pLength );
- typedef void (*StorePresProc)
- (unsigned short xPos, unsigned short yPos );
-
- void PackPresents( unsigned short usNumGifts,
- NextPresProc pNextPresProc,
- StorePresProc pStorePresProc );
-
- void MyPacker( unsigned short usNumGifts,
- long sgaalStorage[WID_DIM][LEN_DIM],
- NextPresProc pNextPresProc,
- StorePresProc pStorePresProc );
-
- /*======================================================
- PackPresents()
-
- Sets up memory and other yukky stuff before calling
- routine to actually do the work.
- ------------------------------------------------------*/
- void PackPresents( unsigned short usNumGifts,
- NextPresProc pNextPresProc,
- StorePresProc pStorePresProc )
- {
- long w, l;
- long lBytes;
-
- sgsGiftsSeen = 0;
- sgsGiftsStored = 0;
- sglItemsOnStack = 0;
- sgsLeftmostPresent = WID_DIM;
- sgsTopmostPresent = LEN_DIM;
-
- lBytes = (MAX_GIFT_DIM+1)
- * (MAX_GIFT_DIM+1) * sizeof( short );
- sgasAreasSeen = (void*)NewPtrClear( lBytes );
- sgasAreasExpected = (void*)NewPtrClear( lBytes );
- sgasStack = (void*)NewPtrClear( (WID_DIM * LEN_DIM )
- * 2 * sizeof( short ) );
- sgalSpace = (void*)NewPtrClear( WID_DIM * LEN_DIM
- * sizeof( long ) );
-
- if ( sgasStack == NULL || sgalSpace == NULL
- || sgasAreasExpected == NULL
- || sgasAreasSeen == NULL )
- DebugStr("\pMemory Allocations Failed" );
-
- /*------------------------------------------------------
- Given the range of inputs we expect to see compute
- the number of presents of each size that we
- expect to be offered.
- ------------------------------------------------------*/
- sgsGiftsSeen = 0;
- sglExpectedCount = 0;
- sglTotalAreaExpected = 0;
- for ( w = MIN_GIFT_DIM; w <= MAX_GIFT_DIM; w++ ) {
- for ( l = MIN_GIFT_DIM;l<=MAX_GIFT_DIM; l++) {
- sgasAreasExpected[ w * l] ++;
- sglTotalAreaExpected += w * l;
- sglExpectedCount++;
- } }
-
- MyPacker( usNumGifts, (void*)sgalSpace,
- pNextPresProc, pStorePresProc );
-
- DisposePtr( (Ptr)sgasAreasSeen );
- DisposePtr( (Ptr)sgasAreasExpected );
- DisposePtr( (Ptr)sgasStack );
- DisposePtr( (Ptr)sgalSpace );
- }
-
- /*------------------------------------------------------
- Utility routines called by packing routine.
- ------------------------------------------------------*/
- Boolean BestPosition( long aalSpace[WID_DIM][LEN_DIM],
- unsigned short usSpaceRemaining,
- unsigned short usWidth,
- unsigned short usLength,
- short *pusX,
- short *pusY );
-
- int LargestGiftDesired( unsigned short usSpaceLeft,
- unsigned short usTotalGifts,
- unsigned short usGiftsRemaining,
- unsigned short usWidth,
- unsigned short usLength );
-
- void RecomputeAreas( long aalSpace[WID_DIM][LEN_DIM],
- unsigned short *pusSpaceRemaining,
- int iHoleSize );
-
-
- /********************************************************
- ********************************************************
- MyPacker()
- ------------------------------------------------------
-
- After getting each present check to see what the
- expected sizes of the next presents will be and
- pick a largest acceptable size. If the present
- meets the size requirement then find the best
- location for it (presents like to sit amoung
- friends or with thier back to the wall!), and
- store it.
-
- *******************************************************
- *******************************************************/
-
- void MyPacker( unsigned short usNumGifts,
- long aalGiftStorage[WID_DIM][LEN_DIM],
- NextPresProc pNextPresProc,
- StorePresProc pStorePresProc )
- {
- unsigned short usSpaceRemaining, usGiftsRemaining;
- unsigned short usWidth, usLength;
- int iLargestGiftDesired, iArea, i;
- int w, l, iHoleSize;
- short X, Y;
-
- usGiftsRemaining = usNumGifts;
- usSpaceRemaining = WID_DIM * LEN_DIM;
-
- /*------------------------------------------------------
- Fill storage array with contiguous area values.
- In the beginning all space is empty and contiguous.
- ------------------------------------------------------*/
- for ( w = 0; w < WID_DIM; w++ )
- for ( l = 0; l < LEN_DIM; l++ )
- aalGiftStorage[w][l] = usSpaceRemaining;
-
- /*------------------------------------------------------
- Get the presents.
- ------------------------------------------------------*/
- while ( usGiftsRemaining ) {
- (pNextPresProc)( &usWidth, &usLength );
- usGiftsRemaining--;
-
- iLargestGiftDesired = LargestGiftDesired(
- usSpaceRemaining, usNumGifts,
- usGiftsRemaining,
- usWidth, usLength );
-
- iArea = usWidth * usLength;
- if ( iArea <= iLargestGiftDesired ) {
-
- if ( BestPosition( aalGiftStorage,
- usSpaceRemaining,
- usWidth, usLength,
- &X, &Y ) ) {
-
- iHoleSize = aalGiftStorage[X][Y];
-
- /*------------------------------------------------------
- Store a gift.
- ------------------------------------------------------*/
- for ( w = 0; w < usWidth; w++ ) {
- for ( l = 0; l < usLength; l++ ) {
- aalGiftStorage[X+w][Y+l]
- = SPACE_USED;
- }
- }
-
- pStorePresProc( (unsigned short)X,
- (unsigned short)Y );
- sgsGiftsStored++;
-
- if ( sgsLeftmostPresent > X )
- sgsLeftmostPresent = X;
- if ( sgsTopmostPresent > Y )
- sgsTopmostPresent = Y;
-
- usSpaceRemaining -= iArea;
-
- RecomputeAreas( aalGiftStorage,
- &usSpaceRemaining,
- iHoleSize );
- }
- }
- if ( usSpaceRemaining == 0 ) {
- #if PRINTF
- printf( " Presents stored == %i.",
- sgsGiftsStored );
- #endif
- return;
- }
- }
- #if PRINTF
- printf( " Presents stored == %i.",
- sgsGiftsStored );
- #endif
- }
-
- /*======================================================
- Push() & Pop() implement a stack for the
- flood fill type algorithm FloodMark to store
- data points on instead of recursing into the heap.
- ------------------------------------------------------*/
- Push( unsigned usX, unsigned usY )
- {
- sgasStack[sglItemsOnStack] = usX;
- sgasStack[sglItemsOnStack+1] = usY;
- sglItemsOnStack += 2;
- }
- Boolean Pop( unsigned short *pusX, unsigned short *pusY )
- {
- if ( sglItemsOnStack ) {
- sglItemsOnStack -= 2;
- *pusX = sgasStack[sglItemsOnStack];
- *pusY = sgasStack[sglItemsOnStack+1];
- return( TRUE );
- }
- return( FALSE );
- }
-
- /*======================================================
- FloodMark()
-
- This is an implementation of the well documented
- Floodfill alorithm for fill irregular shapes with
- paint or other such graphically stuff. Here we
- use it to measure the number of contigious values,
- that match the iValueToMatch, variable,
- in the array. As it encounters each value it
- marks it with the flag MEASURING so that we can
- then go and place the new area value back into
- those positions.
- ------------------------------------------------------*/
- long FloodMark( int iValueToMatch,
- long aal[WID_DIM][LEN_DIM],
- unsigned short X, unsigned short Y,
- Boolean *pbCanFitMinGift )
- {
- long lPixelsFilled = 0;
- int iV = iValueToMatch;
- int l, w;
- Boolean bCanFitMinGift = FALSE;
-
- sglItemsOnStack = 0;
- if ( aal[X][Y] == iV )
- Push( X, Y );
-
- while ( Pop( &X, &Y ) ) {
- aal[X][Y] = MEASURING;
- lPixelsFilled++;
-
- if ( ! bCanFitMinGift ) {
- if ( X + MIN_GIFT_DIM - 1 > WID_DIM )
- goto FAILED_MIN_TEST;
- if ( Y + MIN_GIFT_DIM - 1 > LEN_DIM )
- goto FAILED_MIN_TEST;
- for ( w = 0; w < MIN_GIFT_DIM; w++ )
- for ( l = 0; l < MIN_GIFT_DIM; l++ )
- if ( aal[X+w][Y+l] == SPACE_USED )
- goto FAILED_MIN_TEST;
-
- bCanFitMinGift = TRUE;
- }
-
- FAILED_MIN_TEST:;
- if ( Y > 0 && aal[X][Y-1] == iV )
- Push( X, Y-1 );
- if ( Y+1 < LEN_DIM && aal[X][Y+1] == iV )
- Push( X, Y+1 );
- if ( X > 0 && aal[X-1][Y] == iV )
- Push( X-1, Y );
- if ( X+1 < WID_DIM && aal[X+1][Y] == iV )
- Push( X+1, Y );
- }
- *pbCanFitMinGift = bCanFitMinGift;
- return( lPixelsFilled );
- }
-
- /*======================================================
- RecomputeAreas()
-
- The matrix that holds the current state of stored
- presents contains zeros were presents are located,
- and every other location contains a value that
- describes the area of the contigious region of
- which it is a part. After placing a present in an
- empty region of size X, call this routine with
- iHoleSize = X, so that the area map can be brought
- up to date.
- ------------------------------------------------------*/
- void RecomputeAreas( long aalSpace[WID_DIM][LEN_DIM],
- unsigned short *pusSpaceRemaining,
- int iHoleSize )
- {
- int i,j,k,l, iSmallest;
- long lArea;
- Boolean bCanFitMinGift;
-
- for ( i = 0; i < WID_DIM; i++ ) {
- for ( j = 0; j < LEN_DIM; j++ ) {
-
- if ( aalSpace[i][j] == iHoleSize ) {
- lArea = FloodMark( iHoleSize, aalSpace, i, j,
- &bCanFitMinGift );
-
- if ( ! bCanFitMinGift ) {
- /*------------------------------------------------------
- Remove areas smaller than smallest present.
- ------------------------------------------------------*/
- for( k = 0; k < WID_DIM; k++ )
- for ( l = 0; l < LEN_DIM; l++ )
- if ( aalSpace[k][l] == MEASURING )
- aalSpace[k][l] = SPACE_USED;
- (*pusSpaceRemaining) -= lArea;
- } else {
- for( k = 0; k < WID_DIM; k++ )
- for ( l = 0; l < LEN_DIM; l++ )
- if ( aalSpace[k][l] == MEASURING )
- aalSpace[k][l] = lArea;
- }
- }
- }
- }
- }
-
- /*======================================================
- NeighborCount()
-
- As we all know presents like lots of friends and
- are agoraphobic, so pack them in tight leaving as
- few exposed surfaces as possible. Being next to
- a friend is better than a cold wall, but better to
- cover your rear with a wall then leave it out in
- the open.
- ------------------------------------------------------*/
- int NeighborCount( long aalSpace[WID_DIM][LEN_DIM],
- unsigned short usWidth,
- unsigned short usLength,
- unsigned short usX,
- unsigned short usY )
- {
- unsigned short w, l;
- int iNeighbors;
-
- iNeighbors = 0;
-
- if ( usX + usWidth - 1 < sgsLeftmostPresent ) {
- if ( usX == 0 )
- iNeighbors += (LIKES_WALLS * usLength);
- if ( usX+usWidth == WID_DIM )
- iNeighbors += (LIKES_WALLS * usLength);
- } else {
- for ( l = 0; l < usLength; l++ ) {
- if ( usX == 0 )
- iNeighbors += LIKES_WALLS;
- else if ( aalSpace[usX-1][usY+l] == SPACE_USED )
- iNeighbors += LIKES_OTHERS;
-
- if ( usX+usWidth == WID_DIM )
- iNeighbors += LIKES_WALLS;
- else if ( aalSpace[usX+usWidth][usY+l] == SPACE_USED )
- iNeighbors += LIKES_OTHERS;
- }
- }
-
- if ( usY + usLength - 1 < sgsTopmostPresent ) {
- if ( usY == 0 )
- iNeighbors += (LIKES_WALLS * usWidth);
- if ( usY+usLength == LEN_DIM )
- iNeighbors += (LIKES_WALLS * usWidth);
- } else {
- for ( w = 0; w < usWidth; w++ ) {
- if ( usY == 0 )
- iNeighbors += LIKES_WALLS;
- else if ( aalSpace[usX+w][usY-1] == SPACE_USED )
- iNeighbors += LIKES_OTHERS;
-
- if ( usY+usLength == LEN_DIM )
- iNeighbors += LIKES_WALLS;
- else if ( aalSpace[usX+w][usY+usLength] == SPACE_USED )
- iNeighbors += LIKES_OTHERS;
- }
- }
- return( iNeighbors );
- }
-
- /*======================================================
- BestPosition()
-
- Find the "best" position for this size present.
- If the present does not fit then return FALSE.
- Find the smallest open area that can accomadate
- this package then position it so that it is
- adjacent to as many others, or edges, as possible.
- ------------------------------------------------------*/
- Boolean BestPosition( long aalSpace[WID_DIM][LEN_DIM],
- unsigned short usSpaceRemaining,
- unsigned short usWidth,
- unsigned short usLength,
- short *psX,
- short *psY )
- {
- Boolean bFits = FALSE;
- short sX, sY, w, l;
- int iNeighbors;
- long lThisHole;
- long lSmallestHole = 0x7FFFFFFF;
- int iMostNeighbors = -1;
-
- /*------------------------------------------------------
- 1st package always to the lower right corner.
- ------------------------------------------------------*/
- if ( sgsGiftsStored == 0 ) {
- *psX = WID_DIM - usWidth;
- *psY = LEN_DIM - usLength;
- return( TRUE );
- }
-
- /*------------------------------------------------------
- Check all potential positions for open space.
- ------------------------------------------------------*/
- for ( sX = WID_DIM - usWidth; sX >= 0 ; sX-- ) {
- for ( sY = LEN_DIM - usLength; sY >= 0 ; sY-- ) {
-
- lThisHole = aalSpace[sX][sY];
-
- if ( lThisHole != SPACE_USED
- && lSmallestHole >= lThisHole ) {
-
- for ( w = 0; w < usWidth; w++ ) {
- for ( l = 0; l < usLength; l++ ) {
- if ( aalSpace[sX+w][sY+l] ==
- SPACE_USED ) {
- sY -= ( usLength - l );
- sY ++;
- goto SPACE_NOT_AVAILABLE;
- }
- }
- }
-
- /*------------------------------------------------------
- Count the neighbors, since presents need friends.
- ------------------------------------------------------*/
- iNeighbors = NeighborCount( aalSpace,
- usWidth, usLength, sX, sY );
-
- if ( iNeighbors > iMostNeighbors
- || lSmallestHole > lThisHole ) {
- bFits = TRUE;
- *psX = sX;
- *psY = sY;
- iMostNeighbors = iNeighbors;
- lSmallestHole = lThisHole;
- }
- }
- SPACE_NOT_AVAILABLE:;
- }
- }
- return( bFits );
- }
-
- /*======================================================
- LargestGiftDesired()
-
- To find the largest gift that we wish to accept
- we total all of the areas from smallest to largest
- of the gifts that we expect to get. When the
- expected total approaches the space remaining
- we choose that size as the largest gift to accept.
- ------------------------------------------------------*/
- int LargestGiftDesired( unsigned short usSpaceLeft,
- unsigned short usTotalGifts,
- unsigned short usGiftsRemain,
- unsigned short usWidth,
- unsigned short usLength )
- {
- long lExpected1000;
- long lSpcLeft1000;
- long lRandomModel;
- long lObserved;
- int iSize, iMaxSize;
-
- sgsGiftsSeen++;
- if ( usWidth > MAX_GIFT_DIM
- || usLength > MAX_GIFT_DIM )
- return( 0 );
-
- sgasAreasSeen[usWidth * usLength] += 1;
-
- if ( usGiftsRemain <= 5 )
- return( usSpaceLeft );
-
- iSize = MIN_GIFT_DIM * MIN_GIFT_DIM - 1;
- iMaxSize = MAX_GIFT_DIM * MAX_GIFT_DIM;
- lExpected1000 = 0;
- lSpcLeft1000 = usSpaceLeft * 1000L;
-
- while ( lExpected1000 + iSize * 3 * 1000L
- <= lSpcLeft1000
- && iSize <= iMaxSize ) {
- iSize++;
- lRandomModel = 1000L *
- sgasAreasExpected[iSize] * iSize;
- lObserved = 1000L * sgasAreasSeen[iSize] * iSize;
-
- if ( lRandomModel || lObserved ) {
- lRandomModel = usGiftsRemain * lRandomModel
- / sglExpectedCount;
- lObserved = usGiftsRemain * lObserved
- / sgsGiftsSeen;
-
- /*------------------------------------------------------
- Distribute weight between expected model and
- observed sizes by the proportion of the totals
- gifts that we have already seen.
- ------------------------------------------------------*/
- lRandomModel *= usGiftsRemain;
- lRandomModel /= usTotalGifts;
- lObserved *= (usTotalGifts-usGiftsRemain);
- lObserved /= usTotalGifts;
-
- lExpected1000 += lObserved + lRandomModel;
- }
- }
-
- #if PRINTF
- printf( "<%i-%i>", usSpaceLeft, iSize );
- #endif
- return( iSize );
- }
-